package com.wxit.algorithm.practice;

/**
 * 递归版本的插入排序
 * 未排序区域的下边界
 */
public class InsertSort {

    public static void sort(int[] arr) {
        insertion(arr, 1);
    }

    private static void insertion(int[] a, int low) {

        if (low == a.length) {
            return;
        }

        //先存储，用作临时变量
        //low 未排序区域的左边界
        int t = a[low];
        int i = low - 1; //已排序区域指针右边界

        while (i >= 0 && a[i] > t) {
            a[i + 1] = a[i]; //空出插入位置
            i--;
        }

        //
        if (i + 1 != low) {
            a[i + 1] = t;
        }


        insertion(a, low + 1);
    }
}
